package top.minuy.structure.graph.cc.directed;

import top.minuy.structure.graph.representations.table.Graph;
import top.minuy.structure.graph.search.depth.GraphDFS;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 强联通分量
 * Kosaraju 算法
 *
 * @author Minuy
 * @time 16:52
 * @date 2021/11/27
 */
public class SCC {
    private Graph g;
    private int[] isVisited;

    private int SCCCount = 0;

    public SCC(Graph g) {
        this.g = g;

        this.isVisited = new int[g.V()];
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = -1;
        }

        // 获得倒图
        Graph reG = g.reverse();

        // 求“拓扑排序”
        GraphDFS dfs = new GraphDFS(reG);
        ArrayList<Integer> order = new ArrayList<>();
        for (int v:dfs.post()){
            order.add(v);
        }
        Collections.reverse(order); // 倒序

        // 按“拓扑排序”的倒序来遍历整个图
        for (int v:order){
            if (isVisited[v]==-1){
                dfs(v, SCCCount);
                SCCCount++;
            }
        }
    }

    private void dfs(int v, int CCId) {
        isVisited[v] = CCId;
        for (Integer w : g.adj(v)) {
            if (-1 == isVisited[w]) {
                dfs(w, CCId);
            }
        }
    }

    /**
     * 获取联通分量
     *
     * @return int 整个图的联通分量
     * @author Minuy
     * @date 2021/11/16 17:13
     */
    public int count() {
        return SCCCount;
    }

    /**
     * 判断两个顶点是否联通
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return boolean 是否联通
     * @author Minuy
     * @date 2021/11/16 19:06
     */
    public boolean isStronglyConnected(int v, int w) {
        g.validateVertex(v);
        g.validateVertex(w);
        return isVisited[v] == isVisited[w];
    }

    /**
     * 获取所有的分量
     *
     * @return ArrayList<Integer>[] 列表数组，每个列表里存的是一个联通分量
     * @author Minuy
     * @date 2021/11/16 17:55
     */
    public ArrayList<Integer>[] components() {
        // 创建列表数组
        ArrayList<Integer>[] res = new ArrayList[SCCCount];
        for (int i = 0; i < SCCCount; i++) {
            res[i] = new ArrayList<>();
        }
        // 根据isVisited数组填充列表数组
        for (int v = 0; v < isVisited.length; v++) {
            res[isVisited[v]].add(v);
        }
        return res;
    }
}
